package j2024.j202411;

import java.util.*;

public class j1106 {
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        int left = 0,right = 0,ret = 1;
        while(right<n){
            right = left;
            while(right+1 < n && arr[right+1]-arr[right]<=8){
                right++;
            }
            ret = Math.max(ret,right-left);
            left = right+1;
        }
        System.out.println(ret);
    }

    public static int[] dx = {0,0,-1,1};
    public static int[] dy = {1,-1,0,0};
    public static int[][] dis,cou;
    public static int countPath (int[][] CityMap, int n, int m) {
        // write code here
        dis = new int[n][m];
        cou = new int[n][m];
        int x1=0,x2 = 0,y1 = 0,y2 = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(CityMap[i][j]==1){
                    x1 = i;y1 = j;
                }
                if(CityMap[i][j]==2){
                    x2 = i;y2 = j;
                }
            }
        }
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{x1,y1});
        dis[x1][y1] = 0;
        cou[x1][y1] = 1;
        int ret = 0;
        while (!q.isEmpty()){
            int[] tmp = q.poll();
            int i = tmp[0],j = tmp[1];
            for (int k = 0; k < 4; k++) {
                int x = i+dx[k],y = j+dy[k];
                if(x>=0 && x<n && y>=0 && y<m && CityMap[x][y]!=-1){
                    if(dis[x][y]==-1){
                        dis[x][y] = dis[i][j]+1;
                        cou[x][y] += cou[i][j];
                        q.offer(new int[]{x,y});
                    }else {
                        if(dis[i][j]+1==dis[x][y]){
                            cou[i][j]+=cou[x][y];
                        }
                    }
                }
            }
        }
        return cou[x2][y2];
    }

    public static void main(String[] args) {
        int[][] c = {{0,1,0},{2,0,0}};
        int n = 2,m = 3;
        countPath(c,n,m);
    }
}
